package offer.day33;

public class No57Second_FindContinuousSequence {
    /*
     * 面试题57：和为s的数字
     * 题目二：和为s的连续正数序列
     * 输入一个正数s，打印出所有何为s的连续正数序列（至少含有两个数）。
     * 例如：输入15，由于1+2+3+4+5 = 4+5+6 =7+8 = 15
     * 所以要打印出3个连续序列1~5、4~6、7~8
     *
     * 思路; 可以根据上一个题目的思路继续探究：以s = 9为例
     * 设置两个指针，一个指针指向最小值，一个指针指向最大值，
     * 初始值一个为1，一个为2 ，相加等于3，小于s，则增大big，
     * 判断序列{1，2，3}相加与s的关系，若小于则继续增大big，
     * 判断序列{1，2，3，4}相加与s的关系，若大于则增大small，
     * 判断序列{2，3，4}相加与s的关系，相等，则打印，并且增大big
     * 判断序列{2，3，4，5}相加与s的关系，大于，则增大small，
     * 判断序列{3，4，5}相加与s的关系，大于，则增大small，
     * 判断序列{4，5}相加与s的关系，相等，则打印，
     * 综上所述：
     * 当序列{a,b,c,d,...}当其和的值等于s，zedayin
     * 当其和的值小于s，增大big，让序列包含更多的值
     * 当其和的值大于s，增大small，让序列包含更少的值
     *
     * 也就相当于在和小于s时，一直进行big++
     * 直到大于等于s以后停止增加big，
     * 若等于则打印；
     * 若大于则增加small，减少序列之和，以求出等于s的序列
     *
     * */
    public static void main(String[] args) {
        No57Second_FindContinuousSequence f = new No57Second_FindContinuousSequence();
        int sum = 15;
        System.out.println("和为s的连续正数序列：");
        f.FindContinuousSequence(sum);
    }

    private void FindContinuousSequence(int sum) {
        if (sum < 3) return;
        int small = 1;
        int big = 2;
        int curValue = small + big;
        int mid = (1 + sum) / 2;
        while (small < mid) {
            if (curValue == sum) {
                PrintContinuousSequence(small, big);
            }
            if (curValue > sum) {
                while (small < big) {
                    curValue -= small;
                    small++;
                    if (curValue == sum) {
                        PrintContinuousSequence(small, big);
                    }
                }
            }
            big++;
            curValue += big;


        }
    }

    public void PrintContinuousSequence(int small, int big) {
        for (int i = small; i <= big; i++)
            System.out.print(i + " ");
        System.out.println();
    }
}
